/**
 * @author mrdoob / http://mrdoob.com/
 */
import * as THREE from 'three';
THREE.BufferGeometryUtils = {

  computeTangents: function( geometry ) {

    var index = geometry.index;
    var attributes = geometry.attributes;

    // based on http://www.terathon.com/code/tangent.html
    // (per vertex tangents)

    if ( index === null ||
			 attributes.position === undefined ||
			 attributes.normal === undefined ||
			 attributes.uv === undefined ) {

      console.warn( 'THREE.BufferGeometry: Missing required attributes (index, position, normal or uv) in BufferGeometry.computeTangents()' );
      return;

    }

    var indices = index.array;
    var positions = attributes.position.array;
    var normals = attributes.normal.array;
    var uvs = attributes.uv.array;

    var nVertices = positions.length / 3;

    if ( attributes.tangent === undefined ) {

      geometry.addAttribute( 'tangent', new THREE.BufferAttribute( new Float32Array( 4 * nVertices ), 4 ) );

    }

    var tangents = attributes.tangent.array;

    var tan1 = [], tan2 = [];

    for ( var i = 0; i < nVertices; i ++ ) {

      tan1[ i ] = new THREE.Vector3();
      tan2[ i ] = new THREE.Vector3();

    }

    var vA = new THREE.Vector3(),
      vB = new THREE.Vector3(),
      vC = new THREE.Vector3(),

      uvA = new THREE.Vector2(),
      uvB = new THREE.Vector2(),
      uvC = new THREE.Vector2(),

      sdir = new THREE.Vector3(),
      tdir = new THREE.Vector3();

    function handleTriangle( a, b, c ) {

      vA.fromArray( positions, a * 3 );
      vB.fromArray( positions, b * 3 );
      vC.fromArray( positions, c * 3 );

      uvA.fromArray( uvs, a * 2 );
      uvB.fromArray( uvs, b * 2 );
      uvC.fromArray( uvs, c * 2 );

      var x1 = vB.x - vA.x;
      var x2 = vC.x - vA.x;

      var y1 = vB.y - vA.y;
      var y2 = vC.y - vA.y;

      var z1 = vB.z - vA.z;
      var z2 = vC.z - vA.z;

      var s1 = uvB.x - uvA.x;
      var s2 = uvC.x - uvA.x;

      var t1 = uvB.y - uvA.y;
      var t2 = uvC.y - uvA.y;

      var r = 1.0 / ( s1 * t2 - s2 * t1 );

      sdir.set(
        ( t2 * x1 - t1 * x2 ) * r,
        ( t2 * y1 - t1 * y2 ) * r,
        ( t2 * z1 - t1 * z2 ) * r
      );

      tdir.set(
        ( s1 * x2 - s2 * x1 ) * r,
        ( s1 * y2 - s2 * y1 ) * r,
        ( s1 * z2 - s2 * z1 ) * r
      );

      tan1[ a ].add( sdir );
      tan1[ b ].add( sdir );
      tan1[ c ].add( sdir );

      tan2[ a ].add( tdir );
      tan2[ b ].add( tdir );
      tan2[ c ].add( tdir );

    }

    var groups = geometry.groups;

    if ( groups.length === 0 ) {

      groups = [ {
        start: 0,
        count: indices.length
      } ];

    }

    for ( var i = 0, il = groups.length; i < il; ++ i ) {

      var group = groups[ i ];

      var start = group.start;
      var count = group.count;

      for ( var j = start, jl = start + count; j < jl; j += 3 ) {

        handleTriangle(
          indices[ j + 0 ],
          indices[ j + 1 ],
          indices[ j + 2 ]
        );

      }

    }

    var tmp = new THREE.Vector3(), tmp2 = new THREE.Vector3();
    var n = new THREE.Vector3(), n2 = new THREE.Vector3();
    var w, t, test;

    function handleVertex( v ) {

      n.fromArray( normals, v * 3 );
      n2.copy( n );

      t = tan1[ v ];

      // Gram-Schmidt orthogonalize

      tmp.copy( t );
      tmp.sub( n.multiplyScalar( n.dot( t ) ) ).normalize();

      // Calculate handedness

      tmp2.crossVectors( n2, t );
      test = tmp2.dot( tan2[ v ] );
      w = ( test < 0.0 ) ? - 1.0 : 1.0;

      tangents[ v * 4 ] = tmp.x;
      tangents[ v * 4 + 1 ] = tmp.y;
      tangents[ v * 4 + 2 ] = tmp.z;
      tangents[ v * 4 + 3 ] = w;

    }

    for ( var i = 0, il = groups.length; i < il; ++ i ) {

      var group = groups[ i ];

      var start = group.start;
      var count = group.count;

      for ( var j = start, jl = start + count; j < jl; j += 3 ) {

        handleVertex( indices[ j + 0 ] );
        handleVertex( indices[ j + 1 ] );
        handleVertex( indices[ j + 2 ] );

      }

    }

  },

  /**
	 * @param  {Array<THREE.BufferGeometry>} geometries
	 * @param  {Boolean} useGroups
	 * @return {THREE.BufferGeometry}
	 */
  mergeBufferGeometries: function( geometries, useGroups ) {
    var isIndexed = geometries[ 0 ].index !== null;

    var attributesUsed = new Set( Object.keys( geometries[ 0 ].attributes ) );
    var morphAttributesUsed = new Set( Object.keys( geometries[ 0 ].morphAttributes ) );

    var attributes = {};
    var morphAttributes = {};

    var mergedGeometry = new THREE.BufferGeometry();

    var offset = 0;

    for ( var i = 0; i < geometries.length; ++ i ) {

      var geometry = geometries[ i ];

      // ensure that all geometries are indexed, or none

      if ( isIndexed !== ( geometry.index !== null ) ) return null;

      // gather attributes, exit early if they're different

      for ( var name in geometry.attributes ) {

        if ( ! attributesUsed.has( name ) ) return null;

        if ( attributes[ name ] === undefined ) attributes[ name ] = [];

        attributes[ name ].push( geometry.attributes[ name ] );

      }

      // gather morph attributes, exit early if they're different

      for ( var name in geometry.morphAttributes ) {

        if ( ! morphAttributesUsed.has( name ) ) return null;

        if ( morphAttributes[ name ] === undefined ) morphAttributes[ name ] = [];

        morphAttributes[ name ].push( geometry.morphAttributes[ name ] );

      }

      // gather .userData

      mergedGeometry.userData.mergedUserData = mergedGeometry.userData.mergedUserData || [];
      mergedGeometry.userData.mergedUserData.push( geometry.userData );

      if ( useGroups ) {

        var count;

        if ( isIndexed ) {

          count = geometry.index.count;

        } else if ( geometry.attributes.position !== undefined ) {

          count = geometry.attributes.position.count;

        } else {

          return null;

        }

        mergedGeometry.addGroup( offset, count, i );

        offset += count;

      }

    }

    // merge indices

    if ( isIndexed ) {

      var indexOffset = 0;
      var mergedIndex = [];

      for ( var i = 0; i < geometries.length; ++ i ) {

        var index = geometries[ i ].index;

        for ( var j = 0; j < index.count; ++ j ) {

          mergedIndex.push( index.getX( j ) + indexOffset );

        }

        indexOffset += geometries[ i ].attributes.position.count;

      }

      mergedGeometry.setIndex( mergedIndex );

    }

    // merge attributes

    for ( var name in attributes ) {

      var mergedAttribute = this.mergeBufferAttributes( attributes[ name ] );

      if ( ! mergedAttribute ) return null;

      mergedGeometry.addAttribute( name, mergedAttribute );

    }

    // merge morph attributes

    for ( var name in morphAttributes ) {

      var numMorphTargets = morphAttributes[ name ][ 0 ].length;

      if ( numMorphTargets === 0 ) break;

      mergedGeometry.morphAttributes = mergedGeometry.morphAttributes || {};
      mergedGeometry.morphAttributes[ name ] = [];

      for ( var i = 0; i < numMorphTargets; ++ i ) {

        var morphAttributesToMerge = [];

        for ( var j = 0; j < morphAttributes[ name ].length; ++ j ) {

          morphAttributesToMerge.push( morphAttributes[ name ][ j ][ i ] );

        }

        var mergedMorphAttribute = this.mergeBufferAttributes( morphAttributesToMerge );

        if ( ! mergedMorphAttribute ) return null;

        mergedGeometry.morphAttributes[ name ].push( mergedMorphAttribute );

      }

    }

    return mergedGeometry;

  },

  /**
	 * @param {Array<THREE.BufferAttribute>} attributes
	 * @return {THREE.BufferAttribute}
	 */
  mergeBufferAttributes: function( attributes ) {

    var TypedArray;
    var itemSize;
    var normalized;
    var arrayLength = 0;

    for ( var i = 0; i < attributes.length; ++ i ) {

      var attribute = attributes[ i ];

      if ( attribute.isInterleavedBufferAttribute ) return null;

      if ( TypedArray === undefined ) TypedArray = attribute.array.constructor;
      if ( TypedArray !== attribute.array.constructor ) return null;

      if ( itemSize === undefined ) itemSize = attribute.itemSize;
      if ( itemSize !== attribute.itemSize ) return null;

      if ( normalized === undefined ) normalized = attribute.normalized;
      if ( normalized !== attribute.normalized ) return null;

      arrayLength += attribute.array.length;

    }

    var array = new TypedArray( arrayLength );
    var offset = 0;

    for ( var i = 0; i < attributes.length; ++ i ) {

      array.set( attributes[ i ].array, offset );

      offset += attributes[ i ].array.length;

    }

    return new THREE.BufferAttribute( array, itemSize, normalized );

  },

  /**
	 * @param {Array<THREE.BufferAttribute>} attributes
	 * @return {Array<THREE.InterleavedBufferAttribute>}
	 */
  interleaveAttributes: function( attributes ) {

    // Interleaves the provided attributes into an InterleavedBuffer and returns
    // a set of InterleavedBufferAttributes for each attribute
    var TypedArray;
    var arrayLength = 0;
    var stride = 0;

    // calculate the the length and type of the interleavedBuffer
    for ( var i = 0, l = attributes.length; i < l; ++ i ) {

      var attribute = attributes[ i ];

      if ( TypedArray === undefined ) TypedArray = attribute.array.constructor;
      if ( TypedArray !== attribute.array.constructor ) {

        console.warn( 'AttributeBuffers of different types cannot be interleaved' );
        return null;

      }

      arrayLength += attribute.array.length;
      stride += attribute.itemSize;

    }

    // Create the set of buffer attributes
    var interleavedBuffer = new THREE.InterleavedBuffer( new TypedArray( arrayLength ), stride );
    var offset = 0;
    var res = [];
    var getters = [ 'getX', 'getY', 'getZ', 'getW' ];
    var setters = [ 'setX', 'setY', 'setZ', 'setW' ];

    for ( var j = 0, l = attributes.length; j < l; j ++ ) {

      var attribute = attributes[ j ];
      var itemSize = attribute.itemSize;
      var count = attribute.count;
      var iba = new THREE.InterleavedBufferAttribute( interleavedBuffer, itemSize, offset, attribute.normalized );
      res.push( iba );

      offset += itemSize;

      // Move the data for each attribute into the new interleavedBuffer
      // at the appropriate offset
      for ( var c = 0; c < count; c ++ ) {

        for ( var k = 0; k < itemSize; k ++ ) {

          iba[ setters[ k ] ]( c, attribute[ getters[ k ] ]( c ) );

        }

      }

    }

    return res;

  },

  /**
	 * @param {Array<THREE.BufferGeometry>} geometry
	 * @return {number}
	 */
  estimateBytesUsed: function( geometry ) {

    // Return the estimated memory used by this geometry in bytes
    // Calculate using itemSize, count, and BYTES_PER_ELEMENT to account
    // for InterleavedBufferAttributes.
    var mem = 0;
    for ( var name in geometry.attributes ) {

      var attr = geometry.getAttribute( name );
      mem += attr.count * attr.itemSize * attr.array.BYTES_PER_ELEMENT;

    }

    var indices = geometry.getIndex();
    mem += indices ? indices.count * indices.itemSize * indices.array.BYTES_PER_ELEMENT : 0;
    return mem;

  },

  /**
	 * @param {THREE.BufferGeometry} geometry
	 * @param {number} tolerance
	 * @return {THREE.BufferGeometry>}
	 */
  mergeVertices: function( geometry, tolerance = 1e-4 ) {

    tolerance = Math.max( tolerance, Number.EPSILON );

    // Generate an index buffer if the geometry doesn't have one, or optimize it
    // if it's already available.
    var hashToIndex = {};
    var indices = geometry.getIndex();
    var positions = geometry.getAttribute( 'position' );
    var vertexCount = indices ? indices.count : positions.count;

    // next value for triangle indices
    var nextIndex = 0;

    // attributes and new attribute arrays
    var attributeNames = Object.keys( geometry.attributes );
    var attrArrays = {};
    var morphAttrsArrays = {};
    var newIndices = [];
    var getters = [ 'getX', 'getY', 'getZ', 'getW' ];

    // initialize the arrays
    for ( var name of attributeNames ) {

      attrArrays[ name ] = [];

      var morphAttr = geometry.morphAttributes[ name ];
      if ( morphAttr ) {

        morphAttrsArrays[ name ] = new Array( morphAttr.length ).fill().map( () => [] );

      }

    }

    // convert the error tolerance to an amount of decimal places to truncate to
    var decimalShift = Math.log10( 1 / tolerance );
    var shiftMultiplier = Math.pow( 10, decimalShift );
    for ( var i = 0; i < vertexCount; i ++ ) {

      var index = indices ? indices.getX( i ) : i;

      // Generate a hash for the vertex attributes at the current index 'i'
      var hash = '';
      for ( var j = 0, l = attributeNames.length; j < l; j ++ ) {

        var name = attributeNames[ j ];
        var attribute = geometry.getAttribute( name );
        var itemSize = attribute.itemSize;

        for ( var k = 0; k < itemSize; k ++ ) {

          // double tilde truncates the decimal value
          hash += `${ ~ ~ ( attribute[ getters[ k ] ]( index ) * shiftMultiplier ) },`;

        }

      }

      // Add another reference to the vertex if it's already
      // used by another index
      if ( hash in hashToIndex ) {

        newIndices.push( hashToIndex[ hash ] );

      } else {

        // copy data to the new index in the attribute arrays
        for ( var j = 0, l = attributeNames.length; j < l; j ++ ) {

          var name = attributeNames[ j ];
          var attribute = geometry.getAttribute( name );
          var morphAttr = geometry.morphAttributes[ name ];
          var itemSize = attribute.itemSize;
          var newarray = attrArrays[ name ];
          var newMorphArrays = morphAttrsArrays[ name ];

          for ( var k = 0; k < itemSize; k ++ ) {

            var getterFunc = getters[ k ];
            newarray.push( attribute[ getterFunc ]( index ) );

            if ( morphAttr ) {

              for ( var m = 0, ml = morphAttr.length; m < ml; m ++ ) {

                newMorphArrays[ m ].push( morphAttr[ m ][ getterFunc ]( index ) );

              }

            }

          }

        }

        hashToIndex[ hash ] = nextIndex;
        newIndices.push( nextIndex );
        nextIndex ++;

      }

    }

    // Generate typed arrays from new attribute arrays and update
    // the attributeBuffers
    const result = geometry.clone();
    for ( var i = 0, l = attributeNames.length; i < l; i ++ ) {

      var name = attributeNames[ i ];
      var oldAttribute = geometry.getAttribute( name );
      var attribute;

      var buffer = new oldAttribute.array.constructor( attrArrays[ name ] );
      if ( oldAttribute.isInterleavedBufferAttribute ) {

        attribute = new THREE.BufferAttribute( buffer, oldAttribute.itemSize, oldAttribute.itemSize );

      } else {

        attribute = geometry.getAttribute( name ).clone();
        attribute.setArray( buffer );

      }

      result.addAttribute( name, attribute );

      // Update the attribute arrays
      if ( name in morphAttrsArrays ) {

        for ( var j = 0; j < morphAttrsArrays[ name ].length; j ++ ) {

          var morphAttribute = geometry.morphAttributes[ name ][ j ].clone();
          morphAttribute.setArray( new morphAttribute.array.constructor( morphAttrsArrays[ name ][ j ] ) );
          result.morphAttributes[ name ][ j ] = morphAttribute;

        }

      }

    }

    // Generate an index buffer typed array
    var cons = Uint8Array;
    if ( newIndices.length >= Math.pow( 2, 8 ) ) cons = Uint16Array;
    if ( newIndices.length >= Math.pow( 2, 16 ) ) cons = Uint32Array;

    var newIndexBuffer = new cons( newIndices );
    var newIndices = null;
    if ( indices === null ) {

      newIndices = new THREE.BufferAttribute( newIndexBuffer, 1 );

    } else {

      newIndices = geometry.getIndex().clone();
      newIndices.setArray( newIndexBuffer );

    }

    result.setIndex( newIndices );

    return result;

  }

};
